/**
 * @file 78.Subsets.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-14
 * 
 * @copyright Copyright (c) 2021
 * 
 * 子集问题
 * 收集所有的节点，不仅仅是叶子结点
 * 78.子集 -- 本身无重复 -- 此题有迭代解法，比较巧妙
 * 90.子集II -- 本身有重复，结果需去重
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
private:
    vector<vector<int>> res;
    vector<int> path;

public:
    // 78. 数组无重复，求所有子集
    vector<vector<int>> subsets(vector<int> &nums)
    {
        backtracking78(nums, 0);
        return res;
    }

private:
    void backtracking78(vector<int> &nums, int startIdx)
    {
        // 递归终止可以不写，循环跑到nums.size()自然停止
        res.emplace_back(path);
        for (int i = startIdx; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtracking78(nums, i + 1);
            path.pop_back();
        }
    }

public:
    // 90. 数组有重复，子集不能重
    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end());
        backtracking90(nums, 0);
        return res;
    }

private:
    void backtracking90(vector<int> &nums, int startIdx)
    {
        // 递归终止可以不写，循环跑到nums.size()自然停止
        res.emplace_back(path);
        for (int i = startIdx; i < nums.size(); ++i) {
            if (i > startIdx && nums[i] == nums[i - 1]){
                continue;
            }
            path.push_back(nums[i]);
            backtracking90(nums, i + 1);
            path.pop_back();
        }
    }
};

Solution solve = Solution();

void test78()
{
    vector<int> nums = {1, 2, 3};
    auto res = solve.subsets(nums);
    for (auto &r : res) {
        print(r);
    }
}

void test90()
{
    vector<int> nums = {2, 2, 2};
    auto res = solve.subsetsWithDup(nums);
    for (auto &r : res) {
        print(r);
    }
}

int main()
{
    // test78();
    test90();
    return 0;
}